package tree.递归;

import po.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N具有所有最深节点的最小子树865.java
 * @Description https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/
 * @createTime 2021年07月22日 19:37:00
 */
public class N具有所有最深节点的最小子树865 {
	Map<TreeNode,Integer> deepMap=new HashMap<>();
	Integer maxDeep=Integer.MIN_VALUE;
	public TreeNode subtreeWithAllDeepest(TreeNode root) {
		//先计算每个节点的深度
		deepMap.put(null,-1);
		dfs(root,null);
		//然后获取最深的深度
		for (Integer value : deepMap.values()) {
			maxDeep=Math.max(maxDeep,value);
		}
		//然后获取对应深度的节点
		return getNodeByDeep(root);
	}

	private TreeNode getNodeByDeep(TreeNode node) {
		if (node==null || deepMap.get(node).equals(maxDeep)){
			return node;
		}
		TreeNode left = getNodeByDeep(node.left);
		TreeNode right = getNodeByDeep(node.right);
		//如果左右节点都存在，那么返回这个节点
		if (left != null && right != null) {
			return node;
		}
		//如果左节点为空，右节点存在最大值，就返回左节点
		if (left != null) {
			return left;
		}
		//如果右节点为空，左节点存在最大值，就返回右节点
		if (right != null) {
			return right;
		}
		//如果不存在最大节点，则返回null，表示这个节点为根节点的子树不存在最大节点
		return null;
	}

	private void dfs(TreeNode root,TreeNode parent) {
		if (root == null) {
			return;
		}
		deepMap.put(root,deepMap.get(parent)+1);
		if (root.left != null) {
			dfs(root.left,root);
		}
		if (root.right != null) {
			dfs(root.right,root);
		}
	}
}
